import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-01-18
 * Time: 22:37
 */
public class Main {
    public static int MoreThanHalfNum_Solution(int [] array) {
        //法一：数组排序找到中位数之后再遍历数组找这个中位数，如果次数大于数组一半长度，那么就返回,这种方法比较简单，面试不推荐
      /*  Arrays.sort(array);
        int mid= array[array.length/2];
        int count=0;//记录中位数出现的次数
        for(int num:array){
            if(num==mid){
                count++;
            }
        }
        if(count> array.length/2){
            return mid;
        }
        return 0;*/

        //法二：BM算法，也叫投票算法
        int ret=array[0];//先令第一个数为众数
        int count=1;//记录众数出现的次数
        for(int i=1;i<array.length; i++){
           /* if(count!=0){
                //说明已经有众数存在
                if(ret==array[i]){
                    count++;
                }else{
                    count--;
                }
            }else{
                //说明众数和非众数已经抵消，需要找新的众数
                ret=array[i];
                count=1;//记录新的众数次数为1
            }*/

            //或者这么想，跟容易想到
            if(array[i]==ret){
                count++;
            }else{
                if(count == 0){
                    ret=array[i];
                    count=1;
                }else{
                    count--;
                }
            }
        }
        //再次判断众数ret是否符合条件即超过数组一半长度，也可能出现了众数但是没有超过数组一半，这个是不确定的，所以我们还是需要统计众数出现的次数
        count=0;
        for(int num:array){
            if(num==ret){
                count++;
            }
        }
        return count>array.length/2 ? ret : 0;


    }

    public static void main(String[] args) {
        int[] array={1,2,3,2,2,2,5,4,2};
        System.out.println(MoreThanHalfNum_Solution(array));
    }
}
